# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
from collections import deque
from typing import Optional
from tree_node import TreeNode


class Solution:
    def widthOfBinaryTree(self, root: Optional[TreeNode]) -> int:
        res = 0
        # deque为双向队列。元组中元素1是节点，元素2是数量，表示当前level，节点的索引位置
        q = deque([(root, 1)])
        while q:
            # 获得队列长度
            size = len(q)
            # 遍历之
            for i in range(size):
                # 从左侧开始弹出，获取当前节点和数字
                cur, num = q.popleft()
                # 如果是第一个弹出元组，则记录start的索引
                if i == 0:
                    start = num
                # 如果是最后一个弹出元组，则记录end的索引
                if i == size-1:
                    end = num
                # 遍历当前列的宽度
                res = max(res, end - start + 1)
                # 如果当前元素存在左子树，则记录左子树节点和左子树节点在当前level的索引位置。
                if cur.left:
                    q.append((cur.left, num * 2))
                # 如果当前元素存在右子树，则记录右子树节点和右子树节点在当前level的索引位置
                if cur.right:
                    q.append((cur.right, num * 2 + 1))
        # 相比于s622_2的我的思路，该思路利用了二叉树节点与索引位置的对应关系，免除了处理大量空节点的问题   
        # 相比之下，s622_2的优点则是，可以处理其他种类的树，如三叉树
        return res